INF4480 Spring of 2021 - Project 6: Adaptive Filters

By Olav Fønstelien 2021-04-18


Notes:

In this project we will implement the Least Mean Squares (LMS) and Normalised LMS adaptive filters and apply them on audio recordings of voices (signal) in different types of noise. We will see noise as pure tones which is uncorrelated to the signal, broadband noise uncorrelated to the signal, and at last noise which is correlated to the signal. We will experiment with different filter parameters to achieve the best possible result, allthough that result will not always be very good.

We will begin with some background on adaptive FIR filters and the LMS/NLMS filters. But before we start, let's first set up the Python environment:

We will reuse some functions from Project 3 about power spectrum density estimation, so let's import those

Input and ouput directories:

Introduction

In this assignment we will look at two implementations of the Wiener-Hopf based adaptive filters

FIR Adaptive Filter

We want to extract the signal $d(n)$ from the observation $x(n)$ by filtering out the noise $v(n)$, where $$ x(n) = d(n) + v(n). $$ We do not constrain $d(n),v(n)$ to be stationary, but the stronger the autocorrelation in either one of the signals is, the better. The adaptive FIR filter has the form $\{w_n(k)\}_{k=0}^{p}$ and the signal $d(n)$ is estimated from $x(n)$ by $$ \hat{d}(n) = \sum_{k=0}^p w_n(k) x(n-k). $$ The basic idea behind a noise cancelling filter is similar to that of linear prediction. Only the part of the signal which can be constructed or predicted from its $p$ past values can be separated from noise. Thus, in the ideal case the noise is white and at any time $n$ the signal can be described completely by an MA($p$) ($p$-order moving-average) filter. To make the prediction, we create a reference signal $x_0(n) = x(n-n_0)$ by passing $x(n)$ through a (lagging) timeshift, and optimize the filter $w_n(k)$ such that it minimizes the expected mean-square error $\mathbb{E}(|e(n)|^2)$, where $$ e(n) = x(n) - \sum_{k=0}^p w_n(k) x_0(n-k) = d(n) + v(n) - \hat{d}(n) = \hat{v}(n). $$ The filter $\{w_n(k)\}_{k=0}^{p}$ can then be calculated using the time-varying Wiener-Hopf equation $$ \mathbf{w}_n = \mathbf{R}_{x_0}^{-1}(n) \mathbf{r}_{dx_0}(n), \quad \text{where} \quad \mathbf{R}_{x_0} \in \mathbb{C}^{(p+1) \times (p+1)}, \quad \mathbf{r}_{dx_0} \in \mathbb{C}^{(p+1)}. $$ But, $\mathbf{R}_{x_0}, \mathbf{r}_{dx_0}$ are generally unknown. Instead of approximating them, it may be more computationally efficient to search for the optimum filter weights at each time step $n$ by using the Steepest Descent method. By this method, we initialize the weights to zero; $$ \mathbf{w}_0 = \mathbf{0} $$ and iteratively update the weights by the rule $$ \mathbf{w}_{n+1} = \mathbf{w}_n + \mu \hat{\mathbb{E}}[e(n) \mathbf{x}_0^*(n)] $$ where $\mu$ is some step size, $\hat{\mathbb{E}}[\cdot]$ is the sample-mean over some $L$ samples, and $\mathbf{x}_0^*(n) = [x_0(n-0), x_0(n-1), ..., x_0(n-p)]^H$.

The LMS Filter Algorithm

The LMS filter will approximate the sample mean by using only a single sample, i.e. $L = 1$. The filter weight update rule then becomes $$ \mathbf{w}_{n+1} = \mathbf{w}_n + \mu e(n) \mathbf{x}_0^*(n) $$ which requires only $4p+5$ FLOPs per iteration. The LMS algorithm for estimating the signal $d(n))$ and noise $v(n$ from the observation $x(n) = d(n) + v(n)$ at every time step $n = 0,1,...,N-1$ is as follows:

  1. Initialize $\mathbf{w}_{0} = \mathbf{0}, n = 0$; Then
  2. $\hat{d}(n) \leftarrow \sum_{k=0}^p w_n(k) x_0(n-k)$
  3. $\hat{v}(n) \leftarrow x(n) - \hat{d}(n)$
  4. $\mathbf{w}_{n} \leftarrow \mathbf{w}_{n} + \mu \hat{v}(n) \mathbf{x}_0^*(n)$
  5. $n \leftarrow n + 1$
  6. Repeat from 2.

A Python implementation follows below.

The step size is an important parameter for the algorithm to produce good results. As outlined in Hayes, it is bounded by $$ 0 < \mu < \mu_{max} = \frac{2}{(p+1)\hat{\mathbb{E}}[|x_0(n)|^2]} $$ In practice, we should select a step size which is at least an order of magnitude smaller than the maximum, such that $$ 0 < \mu \le 0.1 \cdot \mu_{max} $$ In Python we find $\mu_{max}$ by this simple method:

Normalized LMS Filter Algorithm

In the standard LMS algorithm above we decide on the step size $\mu$ before we start the calculation, and choose it such that it will be within bounds for the whole sequence $\{x_0(n)\}_{n=0}^{N-1}$. But, since we do not require stationarity in the signals, it might be better to dynamically adjust it depending on the LMS gradient $e(n) \mathbf{x}_0^*(n)$. We calculate a new step size $\mu_n$ at each time $n$ using only the secuence $\{x_0(n)\}_{n=k}^{k+p+1}$. $\mu_n$ is then dynamically bounded; $$ 0 < \mu_n < \mu_{n,max} = \frac{2}{(p+1)\hat{\mathbb{E}}[|x_0(n)|^2]} = \frac{2}{(p+1) \frac{1}{p+1} \sum_{k=0}^p |x_0(n-k)|^2 } = \frac{2}{\mathbf{x}_0^H(n) \mathbf{x}_0(n)} = \frac{2}{||\mathbf{x}_0(n)||^2} $$ This lets us select a normalized step size $\beta \in (0,2)$ such that $$ \mu_n = \frac{\beta}{||\mathbf{x}_0(n)||^2} $$ The NLMS filter weight update rule thus becomes $$ \mathbf{w}_{n+1} = \mathbf{w}_n + \mu_n e(n) \mathbf{x}_0^*(n) = \mathbf{w}_n + \beta e(n) \frac{\mathbf{x}_0^*(n)}{||\mathbf{x}_0(n)||^2} $$ Now, the NLMS algorithm for estimating the signal $d(n))$ and noise $v(n$ from the observation $x(n) = d(n) + v(n)$ at every time step $n = 0,1,...,N-1$ is as follows:

  1. Initialize $\mathbf{w}_{0} = \mathbf{0}, n = 0$; Then
  2. $\hat{d}(n) \leftarrow \sum_{k=0}^p w_n(k) x_0(n-k)$
  3. $\hat{v}(n) \leftarrow x(n) - \hat{d}(n)$
  4. $\mu_n \leftarrow \frac{\beta}{{||\mathbf{x}_0(n)||^2}}$
  5. $\mathbf{w}_{n} \leftarrow \mathbf{w}_{n} + \mu_n \hat{v}(n) \mathbf{x}_0^*(n)$
  6. $n \leftarrow n + 1$
  7. Repeat from 2.

A Python implementation follows below. Note that we have added a small stability factor eps in the denominator when we calculate mu to avoid running into problems when the length of the vector is very small.

At last, let's make some functions which will help us with visualizing the results. The wav files come in 8 bit resolution, but the filters will transform the output data to 64 bit floats, so we should convert the output to 8 bit as well:

Common plotting setup for results:

Assignment 1 - Removal of tone from broad band signal

Assignment 1.1 - Audio clip

We are given three audio clips, each of them with voice distorted by tone. In these cases, the noise $v(n)$ is the voices, while the signal $d(n)$ is the tone distortion, since that has the strongest autocorrelation.

Description of the audio clips from the assignment text:

1.1.1 Audio clip 1 - Undesired carrier on a short wave link

We start by reading in the first file:

As explained above, the signal that we want to filter lies in the noise, $v(n)$, so we keep v. Plots where we compare the input x and the ouput v are shown below. We see that the autocorrelation is very strong in x, while in v, the approximation of noise is quite good, with only a very weak autocorrelation. From the PSD plots we clearly see the distorting tone as a spike at around 2300 Hz in x, while in v it has been attenuated completely. This is also clear from the spectrograms.

We repeat the exercise for NLMS and find that the more or less corresponding parameters perform well, with the same results in audio quality as well as the signal plots, as seen below.

1.1.2 Audio clip 2 - Three consecutive tones on a clean recording of female and male voice

A slightly more interesting case now, with a varying source of noise. We start by reading in the file:

As above, the signal we want to filter is the noise, v. Especially the first two lower tones benefit from increasing the filter order. $p = 50$ works fine, although with the lowest tone, the voice becomes slightly distorted. Keeping the delay $n_0$ at $25$ leads to a fading signal as the tone gets higher, but increasing $n_0$ to $50$ prevents this. The reason is probably that the predicting behaviour of the filter will model also the voices when $n_0$ is too small relative to $p$. Then, the subtraction of $\hat{d}(n)$ from $x(n)$ will also remove parts of the voices in $v(n)$.

Again we plot v against x. We see that autocorrelation is very strong in x, while in v, the approximation of noise by the voices is again quite good. From the PSD plots we clearly see the tones as spikes around 400, 1200 and 2000 Hz, and that they are well attenuated in the filtered signal. This is also confirmed by the spectrograms, which also show the sequence of the three tones in the plot of x. From this we also see the reason why the first tone distorts the voice -- it lies in the same band as the voice, and is therefore to some degree correlated with it. Going back to the PSDs, we see that the FIR filter is slightly high-pass -- frequencies in the filtered signal, below about $500$ Hz are attenuated by $10$ dB or so, which gives the voices a thinner sound.

We repeat the exercise for NLMS and find again that more or less corresponding parameters perform well, with the same results in audio quality as well as the signal plots, as seen below.

1.1.3 Audio clip 3 - Chirp tone on a clean recording of female and male voice

We start by reading in the file:

As above we keep the noise, v. In contrast to above, though, we cannot pick a very long delay for our reference signal, since the chirp tone distortion is constantly changing, and we will not be able to adjust properly unless the delay is short. Above we used $n_0 = 50$, but that is too long here. At $n_0 = 10$ we get good results with $p = 10$, but we need to more agressively adjust the filter coefficients by increasing the step size multiplier to $0.15$. The attenuation is still poorer than in the case with the three consequtive tones, and the distortion in the voices is heavier and does not decrease as the tone leaves the frequency band of the voices.

From the PSD plots we see that in x, the chirp tone is completely dominating, but that a lot of it can be filtered out in v. The PSD is however much flatter than in the prevous case, making the voices sound strange.

We repeat the exercise for NLMS and find again that more or less corresponding parameters perform best. The reults are poorer than for LMS, though, especially towards the end of the clip, when the signal power almost disappears. See spectrogram below. I was not able to find a set of parameters which would alleviate this.

Assignment 2 - Removal of broad band noise from broad band signal

Assignment 2.1 - Sound clip, communications system

Again we are given three audio clips. This time each of them with voice distorted by broadband noise. Since the noise is almost white in these cases, there is a stronger autocorrelation in the voices than in the noise, and therefore we will keep the signal or $d(n)$ part of $x(n)$.est autocorrelation.

Description of the audio clips from the assignment text:

2.1.1 Audio clip 1 - Atmospheric noise that disturbs a short wave communications link

We start by reading in the file:

As we saw in Assignment 1 voice does not have a strong autocorrelation, and separating two signals where neither have a strong correlation to themselves is a much harder problem. But, voice has some correlation to itself, and to be able to extract it, we must base on a short sequence. $n_0 = 5, p = 5$ gives the best restult, even if it still is quite noisy.

The autocorrelation of the reconstructed signal $d(n)$ is plotted below. It overlaps almost perfectly with $x(n)$, which is to expect, given that the noise has zer autocorrelation except at $l = 0$. From the PSD plots we see that the filter is slightly highpass, an effect which we get because the noise in this case lies in the same band as the voice. The spectrograms do not tell too much, but we see that we get some distortion in the 3-4 kHz band which we did not have in the original, which has probably been passed through a lowpass filter.

We repeat the exercise for NLMS and find again that more or less corresponding parameters perform best. The results are poorer than for LMS.

2.1.2 Audio clip 2 - 2 meter FM noise reduction example #1

We start by reading in the file:

This aduio clip is very noisy and it is difficult to find parameters which makes the voice understandable. Using the same parameters as above removes some of the noise in the 0-2 kHz band (where the voice lies), but with increased distortion in the higher frequencies. This is what we saw in the case above as well, and the same effects are seen in the plots below.

We repeat the exercise for NLMS and find again that more or less corresponding parameters perform best. The results are better than for LMS in that the noise in the voice frequency band has been dampened. The PSD plot of the filtered signal shows an interesting pattern. It has several dips separated by about 1 kHz, which are not present in the obersved signal. In the spectrogram we see these as blue traces running thorugh the whole sequence. Comparing the spectrograms there seems to be at least some correlation between the intensity and frequencies of the voice and these dips in the PSD.

2.1.3 Audio clip 3 - VHF FM (NOAA weather) noise reduction example #1

We start by reading in the file:

A slightly less noisy audio recording. Using the same parameters as above turns out to give good results and removes quite much of the noise in the 0-2 kHz band (where the voice lies), but again with increased distortion in the higher frequencies. This is also shown in the PDS of the filtered signal -- most of the power lies in the higher frequencies, in contrast to the observed signal, where most of the energy lies in the 0-2 kHz band. The spectrograms also show this pattern, but we see that much of the power in the voice has also been damped.

As above, the results are better for NLMS than for LMS, and again the PSD plot of the filtered signal the same pattern, with dips some 1 kHz apart. In the spectrogram we see these as blue traces running thorugh the whole sequence. There also seems to be at least some correlation between the intensity and frequencies of the voice and these dips in the PSD.

Assignment 2.2 - Improvement of old audio recordings

Description of the audio clips from the assignment text:

2.2.1 Audio clip 1 - King Edward’s abdication 1936

We start by reading in the file:

This old recording has noise which is correlated with the voice, probably caused by the recording equipment itself. This makes the problem of removing the signal from noise a difficult one, but with a high order filter, we are able to remove much of it. We keep the reconstructed signal $\hat{d}(n)$.

2.2.2 Audio clip 2 - Røros pols fra Brekkeguten

As the case above, this old recording has noise which is correlated with the voice. In addtion it has a pulsating noise pattern which is probably caused by the recording equipment, possibly a wax cylinder. But, by applying a very high order filter, we get decent results with regards to the voice-correlated noice, but not the pulsating pattern.